package personal.leil.learning.recursion;

/**
 * 递归的查找数组中的最大值
 * <p>
 * 使用递归的方式查找出数组中的最大值，从而引出master公式计算递归方法的时间复杂度
 * </p>
 *
 * @author Leil
 * @version 1.0
 * @since 2024-1-2
 */
public class FindMaxByRecursion {

    public static int findMax(int[] arr) {
        if (arr.length == 0) {
            return 0;
        }
        return process(arr, 0, arr.length - 1);
    }

    public static int process(int[] arr, int L, int R) {
        if (L == R) {
            return L;
        }
        int M = L + ((R - L) >> 1);
        int lMaxIndex = process(arr, L, M);
        int rMaxIndex = process(arr, M + 1, R);
        return arr[lMaxIndex] > arr[rMaxIndex] ? lMaxIndex : rMaxIndex;
    }


    /********************* For Test *************************/

    public static void main(String[] args) {
        int[] arr = {34, 23, 43, 54, 234, 54, 2, 4, 564, 54, 6, 2, 342, 43, 4, 243, 43, 45, 333333, 42, 4};
        int index = findMax(arr);
        System.out.println("max index: arr[" + index + "] = " + arr[index]);
    }

}
